#define  _CRT_SECURE_NO_WARNINGS 1

//练习2：二分查找
//给定一个升序的整形数组，在这个数组中查找到指定的值n，找到了就打印n的下标，找不到就打印“找不到”。


#include<stdio.h>

int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };//升序数组
	int k = 10;//查找的数

	//方法一：依次遍历数组--->已知是升序数组(有序数组)，有点浪费资源
	//int i = 0;
	//int sz = sizeof(arr) / sizeof(arr[0]);
	//int flag = 0;
 //   for (i = 0; i < sz; i++)
	//{
	//	if (arr[i] == k)
	//	{
	//		printf("找到了，下标为: %d\n", i);
	//		flag = 1;
	//		break;
	//	}
	//}
 //   if (flag == 0)
	//{
	//	printf("没有找到\n");
	//}


    //方法二：折半查找-->效率高，但条件：数组是有序的
	//数据：1  2  3  4  5  6  7  8  9  10
	//下标：0  1  2  3  4  5  6  7  8  9 
	//     left        mid           right
	int sz = sizeof(arr) / sizeof(arr[0]);
    int left = 0; //0
    int right = sz - 1; //9

	int mid = (left + right) / 2;
	bool flag = false;

	while (left <= right)
    {
        if (arr[mid] == k)
        {
            printf("找到了，下标为: %d\n", mid);
            flag = 1;
            break;
        }
        else if (arr[mid] > k)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
        mid = (left + right) / 2;
    }

    if (!flag)
    {
        printf("没有找到\n"); //这就叫严谨
    }

	//问题：mid = (left + right) / 2
	//如果left + right > int的最大值，就会溢出，导致结果错误
	//解决方案：
	//mid = left + (right - left) / 2; --> 画图直观，mid的值不会超过最大值




	return 0;
}